/*Sort a linked list using insertion sort.
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *newhead = NULL;
        while (head) {
            ListNode *next = head->next;
            insertHelper(head, &newhead);
            head = next;
        }
        return newhead;
    }
private:
    void insertHelper(ListNode *node, ListNode **head) {
        ListNode *prev = NULL, *cur = *head;
        while (cur) {
            if (node->val < cur->val) {
                // insert position found
                if (prev) prev->next = node; 
                node->next = cur; break;
            }
            prev = cur; cur = cur->next;
        }
        if (!prev) *head = node;    // first node
        if (!cur) { // last node
            if (prev) prev->next = node;
            node->next = NULL; 
        }
    }
};
